// https://leetcode.cn/problems/subsets/

// 题干：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集
//       解集 不能 包含重复的子集。你可以按 任意顺序 返回解集

// 示例：输入：nums = [1,2,3]
//       输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

// 碎语：先画决策树，从定义出发，选或者不选
//       全局变量：path，ret，本题没有剪枝，没有check数组
//       dfs这个位置应该添上一个nums[i]，如果不选直接dfs(nums,i+1)
//       path全局，记得恢复现场，有添加才要恢复

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    vector<vector<int>> ret;
    vector<int> path;
public:
    vector<vector<int>> subsets(vector<int>& nums)
    {
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos)
    {
        ret.push_back(path);

        for (int i = pos ; i < nums.size() ; i++){
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }

        // 第二个解法，此时i换为pos
//        if (i == nums.size()){
//            ret.push_back(path);
//            return ;
//        }
//
//        // 选了当前层的数字
//        path.push_back(nums[i]);
//        dfs(nums, i + 1);
//        path.pop_back(); // 回溯
//
//        // 什么都不做，不选直接进入下一层
//        dfs(nums, i + 1);
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,2,3};

    vector<vector<int>> index = sol.subsets(nums);
    for (auto arr : index){
        for (auto num : arr){
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}


